/*
 * $Id: Parser.java 1259 2007-01-09 14:23:47Z tcoupaye $
 *
 * Behavior Protocols extensions for static and runtime checking
 * developed for the Julia implementation of Fractal.
 *
 * Copyright (C) 2006
 *    Formal Methods In Software Engineering Group
 *    Institute of Computer Science
 *    Academy of Sciences of the Czech Republic
 *
 * Copyright (C) 2006 France Telecom
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
 *
 * Contact: ft@nenya.ms.mff.cuni.cz
 * Authors: Jiri Adamek <adamek@nenya.ms.mff.cuni.cz>
 *
 */

package org.objectweb.fractal.bpc.staticchecker.preprocessor;

import java.util.Vector;

import org.objectweb.fractal.bpc.staticchecker.FrameInstance;
import org.objectweb.fractal.bpc.staticchecker.InterfaceInstance;

/**
 * Behavior protocol parser.
 */
public class Parser {

	/* The following constants represent token types. */

	private static final char END = 'e';

	private static final char PREFIX = 'p';

	private static final char SUFFIX = 's';

	private static final char IDENTIFIER = 'i';

	private static final char OPERATOR = 'o';

	/*
	 * The following one-character tokens are represented (in the sense of their
	 * type) by themselves: '.', ',', '(', ')', '{', '}', '[', ']'
	 */

	/* Returns textual representation of a given token type. */
	private static String getTokenText(char token) {
		switch (token) {
		case END:
			return "end of the protocol";
		case PREFIX:
			return "event prefix ('?' or '!')";
		case SUFFIX:
			return "event suffix ('^', '$', or '~')";
		case IDENTIFIER:
			return "identifier";
		case OPERATOR:
			return "operator";
		case '.':
			return "'.'";
		case ',':
			return "','";
		case '(':
			return "'('";
		case ')':
			return "')'";
		case '{':
			return "'{'";
		case '}':
			return "'}'";
		case '[':
			return "'['";
		case ']':
			return "']'";
		default:
			/* this should never occur */
			/* TODO throw an exception here */
			return "!!! UNKNOWN TOKEN - INTERNAL ERROR !!!";
		}
	}
	
	/*
	 * the FrameInstance object representing the frame whose protocol is to be
	 * parsed
	 */
	private FrameInstance frame;
	
	/* the behavior protocol to be parsed */
	private String protocol;

	/* index of the last "read" character in the protocol */
	private int index;

	/*
	 * the token type (one of the constants defined/described above), which was
	 * returned by the getNextToken method the last time
	 */
	private char token;

	/* the position of the current token in the protocol */
	private int position;

	/*
	 * prefix or suffix character - one of the following '?', '!', '^', '$',
	 * '~'; the '#' character is not enumerated here as architecture protocols
	 * are not considered to be analyzed by this parser; the field i set by the
	 * getNextToken method
	 */
	private char fix;

	/* string value: identifier or operator; set by the getNextToken method */
	private String stringValue;

	/*
	 * Returns true if the parameter is one of the operators defined in the
	 * operators aray.
	 */
	private boolean isOperator(String s) {
		for (int i = 0; i < Node.operators.length; i++)
			if (s.equals(Node.operators[i]))
				return true;
		return false;
	}
	
	/*
	 * Returns true if the parameter is a prefix of one of the operators defined
	 * in the operators aray.
	 */
	private boolean isOperatorPrefix(String s) {
		for (int i = 0; i < Node.operators.length; i++)
			if (Node.operators[i].startsWith(s))
				return true;
		return false;
	}
	
	/*
	 * Reads one token and stores its type and other associated values to
	 * appropriate fields of Parser.
	 */
	private char getNextToken() throws ParseErrorException {
		
		Debug.println(4, "Parser.getNextToken()");
		
		/* skip white spaces */
		while (index < protocol.length()
				&& Character.isWhitespace(protocol.charAt(index)))
			index++;
		
		position = index;
		
		/* END */
		if (index == protocol.length()) {
			token = END;
			Debug.println(4, "	return: " + getTokenText(token));
			return token;	
		}
		
		char c = protocol.charAt(index);
		
		/* special symbols represented by themselves */
		if (c == '.' || c == ',' || c == '(' || c == ')'
				|| c == '{' || c == '}' || c == '[' || c == ']') {
			index++;
			token = c;
			Debug.println(4, "	return: " + getTokenText(token));
			return token;
		}
		
		/* prefix */
		if (c == '?' || c == '!') {
			fix = c;
			index++;
			token = PREFIX;
			Debug.println(4, "	return: " + getTokenText(token) + ": '" + fix + "'");
			return token;
		}
		
		/* suffix */
		if (c == '^' || c == '$' || c == '~') {
			fix = c;
			index++;
			token = SUFFIX;
			Debug.println(4, "	return: " + getTokenText(token) + ": '" + fix + "'");
			return token;
		}

		/* identifier */
		StringBuffer sb = new StringBuffer();
		if (Character.isJavaIdentifierStart(c) && c != '$') {
			do {
				sb.append(protocol.charAt(index));
				index++;
			} while (index < protocol.length()
					&& Character.isJavaIdentifierPart(protocol.charAt(index))
					&& protocol.charAt(index) != '$');
			stringValue = sb.toString();
			token = IDENTIFIER;
			Debug.println(4, "	return: " + getTokenText(token) + ": '" + stringValue + "'");
			return token;
		}
		
		/* operator */
		String s =  "";
		while(index < protocol.length()
				&& !Character.isJavaIdentifierPart(protocol.charAt(index))
				&& !Character.isWhitespace(protocol.charAt(index))
				&& isOperatorPrefix(s + protocol.charAt(index))) {
			s = s + protocol.charAt(index);
			index++;
		}
		if (!s.equals("") && isOperator(s)) {
			stringValue = s;
			token = OPERATOR;
			Debug.println(4, "	return: " + getTokenText(token) + ": '" + stringValue + "'");
			return token;
		}
		
		/* it is not any of the known token types */
		throw new ParseErrorException("unknown token: " + s, protocol, position, frame.frameName);
	}


	/*
	 * The following method throws ParseErrorException. It uses the protocol
	 * and position fields of the Parser class as the protocol and atPosition
	 * parameters of the exception constructor. It uses its errorMessage
	 * parameter as the errorMessage parameter of the exception constructor.
	 */  
	private void parseError(String errorMessage) throws ParseErrorException {
		throw new ParseErrorException(errorMessage, this.protocol, this.position, frame.frameName);
	}
	
	/*
	 * The following method throws ParseErrorException. It uses the protocol
	 * field of the Parser class as the protocol
	 * parameter of the exception constructor. It uses its errorMessage and position
	 * parameters as the errorMessage and atPosition parameter of the exception constructor.
	 */  
	private void parseError(String errorMessage, int atPosition) throws ParseErrorException {
		throw new ParseErrorException(errorMessage, this.protocol, atPosition, frame.frameName);
	}
		
	/*
	 * If the current token type is not equal to the parameter of this method,
	 * ParseErrorException is thrown. In the "message" of the exception, the
	 * textual representation of the token returned by getTokenText() is used.
	 */
	private void expect(char expectedToken) throws ParseErrorException {
		if (token != expectedToken)
			parseError(getTokenText(expectedToken) + " expected");
	}

	/*
	 * Returns true iff the method name is of the form <something>_<integer>.
	 */
	public static boolean checkMethodNameExtension(String name)
	{
		if (name.length() < 2 || !Character.isDigit(name.charAt(name.length()-1))) return false;
		int index = name.length() - 2;
		while (index >= 0 && Character.isDigit(name.charAt(index))) index--;
		if (index < 0) return false;
		return name.charAt(index) == '_';
	}
	
	/*
	 * It parses a name of the form <interface_name>.<method_name>
	 */
	private Name parseName() throws ParseErrorException {
		String id1, id2;
		InterfaceInstance ifInst;
		
		expect(IDENTIFIER);
		id1 = stringValue;
		
		ifInst = frame.getInterfaceForName(id1);
		if (ifInst == null) 
			parseError("'" + id1 + "' is not an interface of the '" + frame.frameName + "' component");
		
		getNextToken();
		expect('.');
		getNextToken();
		expect(IDENTIFIER);
		id2 = stringValue;
		
		if (!ifInst.isMethodName(id2)) {
			// parseError("'" + id2 + "' is not a method of the '" + frame.frameName + "::" + ifInst.interfaceName + "' interface");

			/* TODO
			 * This is a temporary hack (the correct code of this if-statement body is the line above).
			 * The hack solves the problem with the method name exstensions of the form _i (i is an integer), which are
			 * added to the protocols by hand and they are not listed as the method names of a particular interface.
			 */
			
			ifInst.addMethodName(id2);
			
			if (!checkMethodNameExtension(id2))
				Debug.println(0, "WARNING: '" + id2
						+ "' is not a method of the '" + frame.frameName + "::"
						+ ifInst.interfaceName
						+ "' interface; adding the name to the list");
			else
				Debug.println(2, "DEBUG: '" + id2
						+ "' silently added to the list of the '"
						+ frame.frameName + "::" + ifInst.interfaceName
						+ "' interface methods");
		}
			
		getNextToken();
		
		return new Name(id1, id2);
	}
	
	/* 
	 * Tests whether given event prefix and suffix are correct for the given type of interface
	 * (provided or required). If it is correct, null is returned, otherwise an error message is returned.
	 */ 
	private String testEvent(boolean isProvided, char prefix, char suffix) {
		if (isProvided) {
			if (prefix == '?' && suffix == '$')
				return "on a provided interface a response cannot be absorbed";
			if (prefix == '!' && suffix == '^')
				return "on a provided interface a requiest cannot be emitted";
		} else {
			if (prefix == '?' && suffix == '^')
				return "on a required interface a request cannot be absorbed";
			if (prefix == '!' && suffix == '$')
				return "on a required interface a response cannot be emitted";
		}
		return null;
	}
	
	/* 
	 * Tests whether given method call prefix is correct for the given type of interface
	 * (provided or required). If it is correct, null is returned, otherwise an error message is returned.
	 */
	private String testCall(boolean isProvided, char prefix) {
		if (isProvided && prefix == '!')
				return "on a provided interface a method call cannot be emitted";
		if ((!isProvided) && prefix == '?')
				return "on a required interface a method call cannot be absorbed";
		return null;
	}
	
	/* It parses an event list of the form event_1, ..., event_n. */
	private Node[] parseEventList() throws ParseErrorException {
		char pr, sf;
		Name nm;
		int startPosition;
		InterfaceInstance ifInst;
		String errorMessage;
		
		Vector v = new Vector();
		
		/* the first one */
		startPosition = position;
		expect(PREFIX);
		pr = fix;
		getNextToken();
		nm = parseName();
		/* TODO add assert(nm.type == Name.INTERFACE) */
		ifInst = frame.getInterfaceForName(nm.interfaceName1);
		/* TODO add assert(ifis != null) */
		expect(SUFFIX);
		sf = fix;
		if ((errorMessage = testEvent(ifInst.isProvided, pr, sf)) != null)
			parseError(errorMessage, startPosition);
		v.add(new Node().setEvent(pr, nm, sf));
		getNextToken();
		
		/* the following */
		while (token == ',') {
			getNextToken();
			startPosition = position;
			expect(PREFIX);
			pr = fix;
			getNextToken();
			nm = parseName();
			/* TODO add assert(nm.type == Name.INTERFACE) */
			ifInst = frame.getInterfaceForName(nm.interfaceName1);
			/* TODO add assert(ifis != null) */
			expect(SUFFIX);
			sf = fix;
			if ((errorMessage = testEvent(ifInst.isProvided, pr, sf)) != null)
				parseError(errorMessage, startPosition);
			v.add(new Node().setEvent(pr, nm, sf));
			getNextToken();
		}
		return (Node[]) v.toArray(new Node[v.size()]);
	}
	
	/*
	 * Parses one level of nesting (parentheses) including recursive parsing of
	 * successive levels of nesting. It returns the parse tree of the parsed
	 * (sub)protocol.
	 */
	private Node parseLevel(int operatorIndex) throws ParseErrorException {
		InterfaceInstance ifInst;
		String errorMessage;
		Debug.println(4, "Parser.parseLevel()");
		Debug.println(4, "	operatorIndex = " + operatorIndex);
		/* parsing an operation ? */
		if (operatorIndex == Node.operators.length) {
			/* NULL, EVENT, CALL, ATOMIC, PARENTHESIS */
			switch (token) {
			case IDENTIFIER:
				/* NULL */
				if (stringValue.equals("NULL")) {
					getNextToken();
					return new Node().setNull();
				} else {
					parseError(getTokenText(PREFIX) + " expected before an identifier");
				}
				/* unreachable */
				return null;
			case PREFIX:
				/* EVENT or CALL */
				int startPosition = position;
				char pr = fix;
				getNextToken();
				Name nm = parseName();
				/* TODO add assert(nm.type == Name.INTERFACE) */
				ifInst = frame.getInterfaceForName(nm.interfaceName1);
				/* TODO add assert(ifis != null) */
				switch (token) {
				case SUFFIX:
					char sf = fix;
					if ((errorMessage = testEvent(ifInst.isProvided, pr, sf)) != null)
						parseError(errorMessage, startPosition);
					getNextToken();
					return new Node().setEvent(pr, nm, sf);
				case '{':
					if ((errorMessage = testCall(ifInst.isProvided, pr)) != null)
						parseError(errorMessage, startPosition);
					getNextToken();
					Node sub = parseLevel(0);
					expect('}');
					getNextToken();
					return new Node().setCall(pr, nm, sub);
				default:
					if ((errorMessage = testCall(ifInst.isProvided, pr)) != null)
						parseError(errorMessage, startPosition);
					return new Node().setCall(pr, nm, null);
				}
			case '(':
				getNextToken();
				Node sub = parseLevel(0);
				expect(')');
				getNextToken();
				return sub;
			case '[':
				getNextToken();
				Node[] events = parseEventList();
				expect(']');
				getNextToken();
				return new Node().setAtomic(events);
			default:
				parseError("NULL, event, call, '(', or '[' expected");
				/* unreachable */
				return null;
			}
		} else {
			/* an operation */
			switch (Node.arity[operatorIndex]) {
			case Node.UNARY:
				Node nd = parseLevel(operatorIndex + 1);
				if (token == OPERATOR
						&& stringValue.equals(Node.operators[operatorIndex])) {
					getNextToken();
					return new Node().setUnary(Node.operators[operatorIndex], nd);
				} else {
					return nd;
				}
			case Node.BINARY:
				Vector v = new Vector();
				Node left, right;
				left = parseLevel(operatorIndex + 1);
				while (token == OPERATOR
						&& stringValue.equals(Node.operators[operatorIndex])) {
					getNextToken();
					right = parseLevel(operatorIndex + 1);
					left = new Node().setBinary(Node.operators[operatorIndex], left,
							right);					
				}
				return left;
			default:
				/* unreachable */
				return null;
			}
		}
	}

	/**
	 * This method parses the behavior protocol given in <code>s</code> and
	 * returns its parse tree.
	 */
	public synchronized Node parse(FrameInstance frame) throws ParseErrorException {
		/* initialization */
		this.frame = frame;
		protocol = frame.protocol;
		index = 0;
		getNextToken();
		/* empty protocol */
		if (token == END)
			return new Node().setNull();
		/*
		 * parse the first level of nesting (parenthesis), including recursive
		 * parsing of successive levels
		 */
		Node result = parseLevel(0);
		expect(END);
		return result;
	}

}
